1. Field of the Invention
The present invention relates to techniques for improving computer system performance. More specifically, the present invention relates to a method and an apparatus that provides selective versioning of memory objects to support multi-dimensional space and time dimensional execution of a computer program.
2. Related Art
As increasing semiconductor integration densities allow more transistors to be integrated onto a microprocessor chip, computer designers are investigating different methods of using these transistors to increase computer system performance. Some recent computer architectures exploit xe2x80x9cinstruction level parallelism,xe2x80x9d in which a single central processing unit (CPU) issues multiple instructions in a single cycle. Given proper compiler support, instruction level parallelism has proven effective at increasing computational performance across a wide range of computational tasks. However, inter-instruction dependencies generally limit the performance gains realized from using instruction level parallelism to a factor of two or three.
Another method for increasing computational speed is xe2x80x9cspeculative executionxe2x80x9d in which a processor executes multiple branch paths simultaneously, or predicts a branch, so that the processor can continue executing without waiting for the result of the branch operation. By reducing dependencies on branch conditions, speculative execution can increase the total number of instructions issued.
Unfortunately, conventional speculative execution typically provides a limited performance improvement because only a small number of instructions can be speculatively executed. One reason for this limitation is that conventional speculative execution is typically performed at the basic block level, and basic blocks tend to include only a small number of instructions. Another reason is that conventional hardware structures used to perform speculative execution can only accommodate a small number of speculative instructions. A further reason is that conventional speculative execution supports only a limited amount of parallelism in the speculative execution process.
What is needed is a method and apparatus that facilitates speculative execution of program instructions at a higher level of granularity so that many more instructions can be speculatively executed.
Additionally, what is needed is a method and an apparatus that supports parallelism in the speculative execution process.
One embodiment of the present invention provides a system that facilitates multi-dimensional space and time dimensional execution of computer programs. The system includes a head thread that executes program instructions and a series of speculative threads that execute program instructions in advance of the head thread, wherein each speculative thread executes program instructions in advance of preceding speculative threads in the series. The head thread accesses a primary version of the memory element and the series of speculative threads access space-time dimensioned versions of the memory element. The system starts by receiving a memory access to the memory element. If the memory access is a write operation by the head thread or a speculative thread, the system determines if a version of the memory element associated with the head thread or speculative thread exists. If not, the system creates a version of the memory element for the thread. Next, the system performs the write operation to the version of the memory element. After performing the write operation, the system checks status information associated with the memory element to determine if the memory element has been read by a following speculative thread in the series of speculative threads. If so, the system causes the following speculative thread and any successive speculative threads in the series to roll back so that the following speculative thread and any successive speculative threads in the series can read a result of the write operation. If not, the system performs the write operation to all successive space-time dimensioned versions of the memory element.
In one embodiment of the present invention, if the memory access is a read operation by a speculative thread, the system updates status information associated with the memory element to indicate the memory element has been read by the speculative thread and determines if a space-time dimensioned version of the memory element associated with the speculative thread exists. If the space-time dimensioned version of the memory element exists, the system reads it. If the space-time dimensioned version of the memory element does not exist, the system reads a space-time dimensioned version of the memory element associated with a preceding speculative thread or the head thread.
In one embodiment of the present invention, accesses to space-time dimensioned versions of the memory element are made indirectly through a pointer associated with the primary version of the memory element. In a variation on this embodiment, the pointer points to an array containing pointers to the space-time dimensioned versions of the memory element.
In one embodiment of the present invention, performing the write operation to all space-time dimensioned versions of the memory element includes checking status information associated with the memory element to determine which space-time dimensioned versions of the memory element have been written to by any speculative thread. Once this is determined, the system writes to space-time time dimensioned versions of the memory element that have not been written to by any speculative thread.
In one embodiment of the present invention, the system performs a join operation between the head thread and the series of speculative threads when the head thread reaches a point in the program where the series of speculative threads began executing. This join operation causes state associated with the series of speculative threads to be merged with state associated with the head thread. In a variation on this embodiment, performing the join operation includes merging the space-time dimensioned versions of the memory element into the primary version of the memory element and discarding the space-time dimensioned versions of the memory element.
In one embodiment of the present invention, causing the speculative thread and any successive speculative threads in the series to roll back includes using a recursive method to cause the speculative thread and any successive speculative threads in the series to roll back.